package leecode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
 * 
 * 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >=
 * g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/assign-cookies
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _455_findContentChildren {

	public static void main(String[] args) {
		_455_findContentChildren app = new _455_findContentChildren();
		System.out.println(app.findContentChildren(new int[] { 1, 2, 3 }, new int[] { 1, 1 }));
		System.out.println(app.findContentChildren(new int[] { 1, 2 }, new int[] { 1, 2, 3 }));
	}

	/**
	 * 
	 * 
	 * @param g 几个孩子
	 * @param s 几块饼干
	 * @return
	 */
	public int findContentChildren(int[] g, int[] s) {
		Arrays.sort(g);
		Arrays.sort(s);
		int numOfCookies = s.length;
		int numOfChildren = g.length;
		int count = 0;
		for (int i = 0, j = 0; i < numOfCookies && j < numOfChildren; i++, j++) {
			// 小孩作为消费方 去 消费饼干，否则增大饼干大小。找出能满足的最小饼干
			while (i < numOfCookies && s[i] < g[j]) {
				i++;
			}
			if (i < numOfCookies) {
				count++;
			}
		}
		return count;
	}

	/**
	 * 我首次写的算法
	 * 
	 * @param g 几个孩子
	 * @param s 几块饼干
	 * @return
	 */
	public int findContentChildren2(int[] g, int[] s) {
		Arrays.sort(g);
		Arrays.sort(s);
		int count = 0;
		int used = 0;
		for (int i = 0; i < s.length; i++) {
			// 饼干的能力
			int cut = s[i];
			for (int j = used; j < g.length; j++) {
				// 孩子的要求
				int ch = g[j];
				if (cut >= ch) {
					count++;
					used++;
					break;
				}
			}
		}
		return count;
	}
}
